/*-
 * Copyright 2012 Guram Dukashvili
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *  notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *  notice, this list of conditions and the following disclaimer in the
 *  documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
//---------------------------------------------------------------------------
#include "sys.h"
#include "hash.h"
//---------------------------------------------------------------------------
static __inline__ uintptr_t static_hash_count()
{
  struct hash * h;
  return sizeof(h->static_hash) / sizeof(h->static_hash[0]);
}
//---------------------------------------------------------------------------
static __inline__ void clear_static_hash(struct hash * h)
{
  intptr_t i;
  for( i = h->size - 1; i >= 0; i-- ) h->static_hash[i] = NULL;
}
//---------------------------------------------------------------------------
struct hash * hash_new(void)
{
  struct hash * h = salloc(sizeof(struct hash),NULL);
  if( h != NULL )
    hash_init(h);
  return h;
}
//---------------------------------------------------------------------------
void hash_init(struct hash * h)
{
  h->hash_chains = h->static_hash;
  h->size = static_hash_count();
  h->count = 0;
  h->node = 0;
  h->estimated_chain_length = 7;
  
  // golden section == 5/8 == 0.625 
  h->threshold_numerator = 625;
  h->threshold_denominator = 1000;

  h->element_hash = NULL;
  h->element_compare = NULL;
  clear_static_hash(h);
}
//---------------------------------------------------------------------------
void hash_set_node(struct hash * h,const void * data,const struct hash_node * node)
{
  h->node = (uintptr_t) node - (uintptr_t) data;
}
//---------------------------------------------------------------------------
void hash_delete(struct hash * h)
{
  hash_destroy(h);
  sfree(h);
}
//---------------------------------------------------------------------------
void hash_destroy(struct hash * h)
{
#if COMPILE_RUNTIME_CHECKS
  if( h->count != 0 ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif
  if( h->size > static_hash_count() )
    sfree(h->hash_chains);
  h->size = static_hash_count();
  h->hash_chains = h->static_hash;
  clear_static_hash(h);
  h->count = 0;
  h->node = 0;
}
//---------------------------------------------------------------------------
struct hash_node ** lookup(const struct hash * h,const void * data)
{
  struct hash_node ** head =
    h->hash_chains + (h->element_hashf(data) & (h->size - 1));
  while( *head != NULL ){
    if( h->element_comparef(data,hash_node2data(h,*head)) == 0 ) break;
    head = &(*head)->next;
  }
  return head;
}
//---------------------------------------------------------------------------
static __inline__ struct hash_node * get_chain(struct hash_node ** hash_chains,uintptr_t chains_count)
{
  struct hash_node * head = NULL, ** p0, ** p1, * a0, * a1;
  
  p0 = hash_chains;
  p1 = p0 + chains_count;

  while( p0 < p1 ){
    a0 = *p0;
    while( a0 != NULL ){
      a1 = a0->next;
      a0->next = head;
      head = a0;
      a0 = a1;
    }
    *p0 = NULL;
    p0++;
  }

  return head;
}
//---------------------------------------------------------------------------
static __inline__ void put_chain(struct hash * h,struct hash_node * head)
{
  struct hash_node ** p0, * a0;

  while( head != NULL ){
    a0 = head->next;
    p0 = lookup(h,hash_node2data(h,head));
    if( *p0 != NULL ){
#if COMPILE_RUNTIME_CHECKS
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
#endif
      abort();
    }
    *p0 = head;
    head->next = NULL;
    head = a0;
  }
}
//---------------------------------------------------------------------------
static __inline__ void optimize_after_insert(struct hash * h)
{
  struct hash_node * head, ** a;
// using golden section == 5/8 as optimization threshold
  uintptr_t count = h->size * h->estimated_chain_length;
  uintptr_t c = count * h->threshold_numerator / h->threshold_denominator, i;
  if( h->count < count + c ) return;

  a = (struct hash_node **)
    salloc((h->size << 1) * sizeof(struct hash_node *),NULL);
  if( a != NULL ){
    head = get_chain(h->hash_chains,h->size);
    if( h->hash_chains != h->static_hash ) sfree(h->hash_chains);
    h->size <<= 1;
    for( i = 0; i < h->size; i++ ) a[i] = NULL;
    h->hash_chains = a;
    put_chain(h,head);
  }
}
//---------------------------------------------------------------------------
static __inline__ void optimize_after_remove(struct hash * h)
{
  struct hash_node * head, ** a;
// using golden section == 5/8 as optimization threshold
  uintptr_t count = h->size * h->estimated_chain_length;
  uintptr_t c = count * h->threshold_numerator / h->threshold_denominator, i;
  if( h->count > count - c ) return;

  if( (h->size >> 1) > static_hash_count() ){
    a = (struct hash_node **) salloc((h->size >> 1) * sizeof(struct hash_node *),NULL);
    if( a != NULL ){
      head = get_chain(h->hash_chains,h->size);
      sfree(h->hash_chains);
      h->size >>= 1;
      for( i = 0; i < h->size; i++ ) a[i] = NULL;
      h->hash_chains = a;
      put_chain(h,head);
    }
  }
  else if( (h->size >> 1) == static_hash_count() ){
    head = get_chain(h->hash_chains,h->size);
    sfree(h->hash_chains);
    h->hash_chains = h->static_hash;
    h->size >>= 1;
    clear_static_hash(h);
    put_chain(h,head);
  }
}
//---------------------------------------------------------------------------
void * hash_insert(struct hash * h,void * data)
{
  struct hash_node ** head = lookup(h,data), * node = *head;
  
  if( node == NULL ){
    node = hash_data2node(h,data);
    *head = node;
    node->next = NULL;
    h->count++;
    optimize_after_insert(h);
    errno = 0;
    return data;
  }
  
  errno = EEXIST;
  return hash_node2data(h,node);
}
//---------------------------------------------------------------------------
void * hash_remove(struct hash * h,void * data)
{
  struct hash_node ** head = lookup(h,data), * node = *head;
  
  if( node != NULL ){
    *head = node->next;
    h->count--;
    optimize_after_remove(h);
    errno = 0;
    return hash_node2data(h,node);
  }
  
  errno = ENOENT;
  return data;
}
//---------------------------------------------------------------------------
void * hash_first(const struct hash * h)
{
  struct hash_node ** p1 = h->hash_chains, ** p2 = p1 + h->size;
  
  while( p1 < p2 && *p1 == NULL ) p1++;
  
  if( *p1 == NULL ){
    errno = ENOENT;
    return NULL;
  }
  
  return hash_node2data(h,*p1);
}
//---------------------------------------------------------------------------
void * hash_lookup(const struct hash * h,const void * data)
{
  struct hash_node ** p = lookup(h,data);
  
  if( *p == NULL ){
    errno = ENOENT;
    return (void *) data;
  }
  
  errno = EEXIST;
  return hash_node2data(h,*p);
}
//---------------------------------------------------------------------------
uintptr_t hash_max_chain_length(const struct hash * h)
{
  uintptr_t max = 0, m;
  intptr_t i;
  for( i = h->size - 1; i >= 0; i-- ){
    struct hash_node ** p;
    for( m = 0, p = h->hash_chains + i; *p != NULL; p = &(*p)->next, m++ );
    if( m > max ) max = m;
  }
  return max;
}
//---------------------------------------------------------------------------
uintptr_t hash_min_chain_length(const struct hash * h)
{
  uintptr_t min = ~(uintptr_t) 0, m;
  intptr_t i;
  for( i = h->size - 1; i >= 0; i-- ){
    struct hash_node ** p;
    for( m = 0, p = h->hash_chains + i; *p != NULL; p = &(*p)->next, m++ );
    if( m < min ) min = m;
  }
  return min;
}
//---------------------------------------------------------------------------
uintptr_t hash_avg_chain_length(const struct hash * h)
{
  uintptr_t avg = 0, m;
  intptr_t i;
  for( i = h->size - 1; i >= 0; i-- ){
    struct hash_node ** p;
    for( m = 0, p = h->hash_chains + i; *p != NULL; p = &(*p)->next, m++ );
    avg += m;
  }
  return h->size > 0 ? avg / h->size : 0;
}
//---------------------------------------------------------------------------
